import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class Fig {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3), new Edge(v2), new Edge(v6));
        v2.edges = List.of(new Edge(v4));
        v3.edges = List.of(new Edge(v4), new Edge(v6));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5));

//        dfs2(v1);
        bfs(v1);
    }


    // DFS:深度优先遍历
    // 递归实现
    public static void dfs(Vertex v){
        v.visited = true;
        System.out.println(v.name);
        for (Edge edge : v.edges){
            if (!edge.linked.visited){
                dfs(edge.linked);
            }
        }
    }

    // 非递归
    public static void dfs2(Vertex v){
        LinkedList<Vertex> stack = new LinkedList<>();
        stack.push(v);
        while (!stack.isEmpty()){
            Vertex ver = stack.pop();
            ver.visited = true;
            System.out.println(ver.name);
            for (Edge edge : ver.edges){
                if (!edge.linked.visited){
                    stack.push(edge.linked);
                }
            }
        }
    }

    // BFS:广度优先遍历
    public static void bfs(Vertex v){
        LinkedList<Vertex> queue = new LinkedList<>();
        queue.offer(v);
        v.visited = true;
        while (!queue.isEmpty()){
            Vertex ver = queue.poll();
            System.out.println(ver.name);
            for (Edge edge : ver.edges){
                if (!edge.linked.visited){
                    edge.linked.visited = true;
                    queue.offer(edge.linked);
                }
            }
        }
    }
}

// 顶点
class Vertex{
    String name;
    List<Edge> edges;
    boolean visited; // 判断是否被访问过
    int inDegree; // 判断入度
    int status; // 状态 0-未访问 1-访问中 2-访问过，用在拓扑排序
    private final int INF = Integer.MAX_VALUE; // 距离
    int dist = INF;
    Vertex prev = null; // 保存前一节点

    public Vertex(String name) {
            this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Vertex vertex = (Vertex) o;
        return Objects.equals(name, vertex.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

// 边
class Edge{
    Vertex linked;
    int weight; // 权重

    public Edge(Vertex linked){
            this(linked, 1);
    }

    public Edge(Vertex linked, int weight){
            this.linked = linked;
            this.weight = weight;
    }
}

